<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            let arr = [1, 3, 4, 5, 2, 111, 19, 100];
            // <!-- 冒泡排序 -->
            // function bubbleSort(arr) {
            //     for (let i = 0; i < arr.length - 1; i++) {
            //         for (let j = 0; j < arr.length - 1 - i; j++) {
            //             if (arr[j] > arr[j + 1]) {
            //                 let temp = arr[j];
            //                 arr[j] = arr[j + 1];
            //                 arr[j + 1] = temp;
            //             }
            //         }
            //     }
            //     return arr;
            // }
            // console.log(bubbleSort(arr));
            // // 快速排序
            // function quickSort(arr1) {
            //     if (arr1.length < 2) return arr1;
            //     let left = [],
            //         right = [];
            //     let mainIndex = Math.floor(arr1.length / 2);
            //     let mainItem = arr1.splice(mainIndex, 1)[0];
            //     for (let i = 0; i < arr1.length; i++) {
            //         if (arr1[i] < mainItem) {
            //             left.push(arr1[i]);
            //         } else {
            //             right.push(arr1[i]);
            //         }
            //     }
            //     return quickSort(left).concat([mainItem], quickSort(right));
            // }
            // console.log(quickSort(arr));

            // let arr2 = [1, 4, 5, 2, 3, 10, 9];
            // // 插入排序
            // function insertSort(arr) {
            //     let temp;
            //     for (let i = 0; i < arr.length; i++) {
            //         let temp = arr[i];
            //         for (let j = i; j >= 0; j--) {
            //             if (arr[j - 1] > temp) {
            //                 arr[j] = arr[j - 1];
            //             } else {
            //                 arr[j] = temp;
            //                 break;
            //             }
            //         }
            //     }
            //     return arr;
            // }
            // console.log(insertSort(arr2));
            // // 选择排序
            // function selectSort(arr) {
            //     let index;
            //     for (let i = 0; i < arr.length; i++) {
            //         index = i;
            //         for (let j = i; j < arr.length; j++) {
            //             if (arr[i] > arr[j]) {
            //                 index = j;
            //             }
            //         }
            //         [arr[i], arr[index]] = [arr[index], arr[i]];
            //     }
            //     return arr;
            // }
            // console.log(selectSort(arr2));

            // // 归并排序
            // function merge(left, right) {
            //     let temp = [];
            //     while (left.length && right.length) {
            //         if (left[0] > right[0]) {
            //             temp.push(right.shift());
            //         } else {
            //             temp.push(left.shift());
            //         }
            //     }
            //     return temp.concat(left, right);
            // }

            // function mergeSort(arr) {
            //     if (arr.length < 2) return arr;
            //     let mid = Math.floor(arr.length / 2);
            //     let left = arr.slice(0, mid);
            //     let right = arr.slice(mid);
            //     return merge(mergeSort(left), mergeSort(right));
            // }
            // console.log(mergeSort(arr2));

            // // 希尔排序
            // function shellSort(arr) {
            //     let temp;
            //     for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
            //         for (let j = gap; j < arr.length; j++) {
            //             temp = arr[j];
            //             while (j - gap > 0 && arr[j - gap] > temp) {
            //                 arr[j] = arr[j - gap];
            //                 j = j - gap;
            //             }
            //             arr[j] = temp;
            //         }
            //     }
            //     return arr;
            // }
            // console.log(shellSort(arr2));

            // // 计数排序
            // function countSort(arr) {
            //     let min = Math.min(...arr);
            //     let max = Math.max(...arr);
            //     let newArr = [];
            //     for (let i = 0; i < arr.length; i++) {
            //         newArr[arr[i]] = newArr[arr[i]] + 1 || 1;
            //     }
            //     let index = 0;
            //     for (let i = min; i < max; i++) {
            //         while (newArr[i] > 0) {
            //             arr[index++] = i;
            //             arr[i]--;
            //         }
            //     }
            //     return arr;
            // }
            // console.log(countSort(arr2));

            // 基数排序
            function radixSort(arr) {
                // mod 和 dev用于每次取出个位，十位百位上的数
                let counter = [],
                    mod = 10,
                    dev = 1;
                // 找出当前的数组中的最大值
                let max = Math.max(...arr);
                // 并且确定最大比较位数
                let maxDigit = 0;
                while (max != 0) {
                    max = parseInt(max / 10);
                    maxDigit++;
                }
                for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
                    for (let j = 0; j < arr.length; j++) {
                        let bucket = parseInt((arr[j] % mod) / dev);
                        if (counter[bucket] == null) {
                            counter[bucket] = [];
                        }
                        counter[bucket].push(arr[j]);
                    }
                    let pos = 0;
                    for (let j = 0; j < counter.length; j++) {
                        let value = null;
                        if (counter[j] != null) {
                            while ((value = counter[j].shift()) != null) {
                                arr[pos++] = value;
                            }
                        }
                    }
                }
                return arr;
            }
            console.log(radixSort(arr));
        </script>
    </body>
</html>
